package graphmanip.collapsing;


import graphmanip.CollapsingMethod;

import java.awt.Point;
import java.util.ArrayList;

import user.data.Data;
import guiobjects.Observation;

import commonfunctions.*;

public class CrossingSetCollapsing extends CollapsingMethod 
{
	int[] myFrameMappings = new int[0];
	private boolean isInFrames;
	public CrossingSetCollapsing()
	{
		isInFrames = false;
	}
	public CrossingSetCollapsing(ArrayList<Observation> obs)
	{
		isInFrames = true;
		myFrameMappings = new int[obs.size()];
		int maxCamNum = 0;
		for (int i = 0; i < obs.size(); i++)
			maxCamNum = (maxCamNum < obs.get(i).camera)?obs.get(i).camera:maxCamNum;
		for (int i = 0; i < obs.size(); i++)
			myFrameMappings[i] = (obs.get(i).frameNum - 1) * (maxCamNum + 1) + obs.get(i).camera;
	}
	public ArrayList<ArrayList<Integer>> collapse(Matrix weights) 
	{
		if (weights.length() != myFrameMappings.length)
			isInFrames = false;
		ArrayList<Integer> listOfNegatives = new ArrayList<Integer>();
		for (int i = 0; i < weights.length(); i++)
		{
			boolean hasPositive = false;
			for (int j = 0; j < weights.length(); j++)
			{
				if (weights.get(i, j) >= 0.0)
				{
					hasPositive = true;
					break;
				}
			}
			if (!hasPositive)
				listOfNegatives.add(i);
		}
		ArrayList<Point> output = new ArrayList<Point>();
		HungarianAlgo h = new HungarianAlgo(weights);
		int[] nodeTimeMappings;
		if (isInFrames)
			nodeTimeMappings = myFrameMappings;
		else
			nodeTimeMappings = Functions.getTimeMappings(weights);
		//TODO: after here
		int maxMapping = 0;
		for (int i = 0; i < nodeTimeMappings.length; i++)
		{
			if (nodeTimeMappings[i] > maxMapping)
				maxMapping = nodeTimeMappings[i];
		}
		ArrayList<ArrayList<Integer>> nodeGroupings = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i <= maxMapping; i++)
			nodeGroupings.add(new ArrayList<Integer>());
		for (int i = 0; i < nodeTimeMappings.length; i++)
			nodeGroupings.get(nodeTimeMappings[i]).add(i);
		Matrix groupWeights = new Matrix(maxMapping + 1);
		for (int i = 0; i < nodeGroupings.size(); i++)
		{
			for (int j = i + 1; j < nodeGroupings.size(); j++)
			{
				double value = 0.0;
				ArrayList<Point> temporaryPoints = new ArrayList<Point>();
				ArrayList<Double> temporaryVals = new ArrayList<Double>();
				ArrayList<Integer> firstGroup = nodeGroupings.get(i);
				ArrayList<Integer> secondGroup = nodeGroupings.get(j);
				ArrayList<Point> chosenEdges = getBestEdges(weights, h,
						temporaryPoints, temporaryVals, firstGroup, secondGroup);
				for (int l = 0; l < chosenEdges.size(); l++)
					value += Math.abs(weights.get(chosenEdges.get(l).x, chosenEdges.get(l).y));
				for (int l = 0; l < temporaryPoints.size(); l++)
					weights.set(temporaryVals.get(l), temporaryPoints.get(l).x, temporaryPoints.get(l).y);
				temporaryPoints = new ArrayList<Point>();
				temporaryVals = new ArrayList<Double>();
				invertVals(weights, firstGroup, secondGroup);
				chosenEdges = getBestEdges(weights, h,
						temporaryPoints, temporaryVals, firstGroup, secondGroup);
				for (int l = 0; l < chosenEdges.size(); l++)
					value += Math.abs(weights.get(chosenEdges.get(l).x, chosenEdges.get(l).y));
				for (int l = 0; l < temporaryPoints.size(); l++)
					weights.set(temporaryVals.get(l), temporaryPoints.get(l).x, temporaryPoints.get(l).y);
				invertVals(weights, firstGroup, secondGroup);
				groupWeights.set(value, i, j);
				groupWeights.set(value, j, i);
			}
		}

		ArrayList<Thread> threadList = new ArrayList<Thread>();

		double numProcesses = Data.numThreads;
		double workPerProcess = ((double)(nodeGroupings.size() * (nodeGroupings.size() + 1)))
								/ (2 * numProcesses);
		
		int lastNum = nodeGroupings.size();
		//TODO: gets stuck before here
		while (lastNum > 0)
		{
			//the following is used to allocate load.
			double x = ((double)(lastNum) * (lastNum + 1))/2;
			int current = lastNum;
			lastNum = (int)(-0.5 + Math.sqrt(0.25 - 2.0 * (workPerProcess - x)));
			if (current == lastNum)
				lastNum--;
			threadList.add(new EvenSmarterHungarianThreadObject(weights, output, h, nodeGroupings, 
					groupWeights, nodeGroupings.size() - current, Math.min(nodeGroupings.size() - lastNum, 
							nodeGroupings.size())));
		}
		for (int i = 0; i < threadList.size(); i++)
		{
			threadList.get(i).start();
		}
		for (int i = 0; i < threadList.size(); i++)
		{
			while(threadList.get(i).isAlive())
			{
				try {
					Thread.sleep(1000);
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
		}
		
		ArrayList<ArrayList<Integer>> toReturn = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i < output.size(); i++)
		{
			toReturn.add(new ArrayList<Integer>());
			if (output.get(i) != null)
			{
				toReturn.get(i).add(output.get(i).x);
				toReturn.get(i).add(output.get(i).y);
			}
			else
				System.out.println("Null element.");
		}
		return toReturn;
	}

	private void invertVals(Matrix weights, ArrayList<Integer> firstGroup,
			ArrayList<Integer> secondGroup) {
		for (int k = 0; k < firstGroup.size(); k++)
		{
			for (int l = 0; l < secondGroup.size(); l++)
			{
				weights.set(weights.get(firstGroup.get(k), secondGroup.get(l)) * -1, 
						firstGroup.get(k), secondGroup.get(l));
				weights.set(weights.get(secondGroup.get(l), firstGroup.get(k)) * -1, 
						secondGroup.get(l), firstGroup.get(k));
			}
		}
	}

	public static ArrayList<Point> getBestEdges(Matrix weights, HungarianAlgo h,
			ArrayList<Point> temporaryPoints, ArrayList<Double> temporaryVals,
			ArrayList<Integer> firstGroup, ArrayList<Integer> secondGroup) {
		ArrayList<Point> edgesToTest = new ArrayList<Point>();
		for (int k = 0; k < firstGroup.size(); k++)
		{
			for (int l = 0; l < secondGroup.size(); l++)
			{
				if (weights.get(firstGroup.get(k), secondGroup.get(l)) > 0.0)
					edgesToTest.add(new Point(firstGroup.get(k), secondGroup.get(l)));
				else if (weights.get(secondGroup.get(l), firstGroup.get(k)) > 0.0)
				{
					temporaryVals.add(weights.get(secondGroup.get(l), firstGroup.get(k)));
					weights.set(weights.get(secondGroup.get(l), firstGroup.get(k)), 
											firstGroup.get(k), secondGroup.get(l));
					edgesToTest.add(new Point(firstGroup.get(k), secondGroup.get(l)));
					temporaryPoints.add(new Point(firstGroup.get(k), secondGroup.get(l)));
				}
			}
		}
		ArrayList<Point> chosenEdges = h.hungarianAlgorithm(edgesToTest);
		return chosenEdges;
	}
	
	private class EvenSmarterHungarianThreadObject extends Thread
	{
		Matrix myWeights; 
		ArrayList<Point> myOutput;
		HungarianAlgo myH;
		ArrayList<ArrayList<Integer>> myNodeGroupings;
		Matrix myGroupWeights;
		int myBeginI;
		int myEndI;
		public EvenSmarterHungarianThreadObject(Matrix weights, ArrayList<Point> output,
				HungarianAlgo h, ArrayList<ArrayList<Integer>> nodeGroupings,
				Matrix groupWeights, int beginI, int endI)
		{
			myWeights = new Matrix(weights);
			myOutput = output;
			myH = h;
			myNodeGroupings = nodeGroupings;
			myGroupWeights = new Matrix(groupWeights);
			myBeginI = beginI;
			myEndI = endI;
		}
		public void run() 
		{
			for (int myI = myBeginI; myI < myEndI; myI++)
			{
				for (int j = myI + 1; j < myNodeGroupings.size(); j++)
				{
					double amountToBeat = (new FlowGraph()).maxFlow(myGroupWeights, myI, j);
					ArrayList<Point> temporaryPoints = new ArrayList<Point>();
					ArrayList<Double> temporaryVals = new ArrayList<Double>();
					ArrayList<Integer> firstGroup = myNodeGroupings.get(myI);
					ArrayList<Integer> secondGroup = myNodeGroupings.get(j);
					ArrayList<Point> chosenEdges = CrossingSetCollapsing.getBestEdges(myWeights, myH,
							temporaryPoints, temporaryVals, firstGroup, secondGroup);
					double sum = 0;
					for (int k = 0; k < chosenEdges.size(); k++)
						sum += myWeights.get(chosenEdges.get(k).x, chosenEdges.get(k).y);
					double amountToBeLessThan = sum - amountToBeat;
					for (int k = 0; k < chosenEdges.size(); k++)
					{
						double originalAmount = myWeights.get(chosenEdges.get(k).x, chosenEdges.get(k).y);
						myWeights.set(0.0, chosenEdges.get(k).x, chosenEdges.get(k).y);
						ArrayList<Point> newEdges = myH.hungarianAlgorithm(chosenEdges);
						double sumOfNewEdges = 0.0;
						for (int l = 0; l < newEdges.size(); l++)
							sumOfNewEdges += myWeights.get(newEdges.get(l).x, newEdges.get(l).y);
						if (sumOfNewEdges < amountToBeLessThan)
							myOutput.add(new Point(chosenEdges.get(k).x, chosenEdges.get(k).y));
						myWeights.set(originalAmount, chosenEdges.get(k).x, chosenEdges.get(k).y);
					}
					for (int k = 0; k < temporaryVals.size(); k++)
						myWeights.set(temporaryVals.get(k), temporaryPoints.get(k).x, temporaryPoints.get(k).y);
				}
			}
		}
	}
}
